package com.ry.day1129;

import java.util.Arrays;

public class LC562 {

    static class Solution {
        /**
         * @param nums: an integer array and all positive numbers, no duplicates
         * @param target: An integer
         * @return: An integer
         */
        public int backPackIV(int[] nums, int target) {
            return shacache(nums,target);
        }

        public int shacache(int[] nums,int target){
            int n= nums.length;
            int[][] dp = new int[n+1][target+1];
            for (int i = 0; i <=n ; i++) {
                Arrays.fill(dp[i],-1);
            }

            return f1(nums,0,target,dp);
        }

        public int f1(int[] nums,int idx,int rest,int[][] dp){
            if(rest<0) return -1;
            if(idx ==nums.length) {
                return rest ==0 ?1:0;
            }

            if(dp[idx][rest] !=-1)
                return dp[idx][rest];

            int ans =0;
            for (int zhang = 0; zhang*nums[idx] <=rest ; zhang++) {
                int next= f1(nums,idx+1,rest-zhang*nums[idx],dp);
                if(next!=-1){
                    ans+=next;
                }
            }

            dp[idx][rest] = ans;
            return ans;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.backPackIV(new int[]{2,3,6,7},7)); //2
        System.out.println(obj.backPackIV(new int[]{2,3,4,5},7)); //3
    }
}
